今天也帶來一道經典題目：

黑白羊過橋問題

黑、白羊兩族需要過橋，如圖:

規則:

每次只能有一隻羊移動，
移動方式有:
1. 向前一格走到前方空格
2. 跳過對方一隻羊進入前面的一個空位(不可跳過兩隻羊)

牠們現在站的位置應該是這樣:
黑羊 黑羊 黑羊 空格 白羊 白羊 白羊
你可以假設黑羊=1，白羊=-1，空格=0，
用一個列表表示為[1,1,1,0,-1,-1,-1]。

注意若此時亂動的話，羊群便會阻塞而過不了橋，
比如說前兩隻黑羊各往前走一格，
變成[1,0,1,1,-1,-1,-1]。
那就真的別想過橋了。

好在現在有個完美的解法可以讓黑、白羊都過橋，
可以經過若干次移動後，讓羊的位置變為
白羊 白羊 白羊 空格 黑羊 黑羊 黑羊
列表表示就是 [-1,-1,-1,0,1,1,1]

參考解法

def goatmove(goats, move=()):
    if goats==[-1,-1,-1,0,1,1,1]: #遞迴終止條件
        return [move]
    ans = []
    length = len(goats)
    for i in range(length): #檢查每隻羊是否能動
        if i<length-2 and goats[i]==1 and goats[i+1]==-1 and goats[i+2]==0: #向右跳
            new_goats = goats[:]
            new_goats[i], new_goats[i+2] = new_goats[i+2], new_goats[i]
            ans+= goatmove(new_goats, move+(i,"向右跳"))
        if i>1 and goats[i-2]==0 and goats[i-1]==1 and goats[i]==-1: #向左跳
            new_goats = goats[:]
            new_goats[i], new_goats[i-2] = new_goats[i-2], new_goats[i]
            ans+= goatmove(new_goats, move+(i,"向左跳"))
        if i<length-1 and goats[i]==1 and goats[i+1]==0: #向右走
            new_goats = goats[:]
            new_goats[i], new_goats[i+1] = new_goats[i+1], new_goats[i]
            ans+= goatmove(new_goats, move+(i,"向右走"))
        if i>0 and goats[i-1]==0 and goats[i]==-1: #向左走
            new_goats = goats[:]
            new_goats[i], new_goats[i-1] = new_goats[i-1], new_goats[i]
            ans+= goatmove(new_goats, move+(i,"向左走"))
    return ans
    
goats = [1,1,0,1,-1,-1,-1]
print(goatmove(goats))

輸入初始位置[1,1,0,1,-1,-1,-1]做測試
結果:[(4, '向左跳', 5, '向左走', 3, '向右跳', 1, '向右跳', 0, '向右走', 2, '向左跳', 4, '向左跳', 6, '向左跳', 5, '向右走', 3, '向右跳', 1, '向右跳', 2, '向左走', 4, '向左跳', 3, '向右走')]
找到一組解